#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#define NAME_LEN 32            //进程名
#define MEM_SIZE 1024          //内存大小
#define MEM_START 0            //起始位置
#define MATE_FIR 1             //定义首次适配算法
#define DATA_NUM 5            //定义产生数据的组数
#define PROCESS_NUM 3          //进程数
#define PROCESS_SIZE 10        //进程大小
#define ALLOC_SIZE 100         //随机分配最大值

/*记录内存空间使用情况，每个进程分配到的内存块描述*/
typedef struct allocated_block{
    int pid;
    int size;
    int start_addr;
    char process_name[NAME_LEN];
    struct allocated_block *next;
}AB;
/*记录空闲分区，描述每一个空闲块的数据结构*/
typedef struct free_block_type{
    int size;
    int start_addr;
    struct free_block_type *next;
}FBT;
/*描述每个进程结构*/
typedef struct Process{
    int size;
    int pid;
    char process_name[NAME_LEN];
}PRO;

FBT *free_block;//指向内存中空闲块链表的首指针
/*进程分配内存块链表的首指针*/
AB *allocated_block_head = NULL;

static int pid = 0;          /*初始pid*/

int mem_size = MEM_SIZE;     //内存大小
int ma_algorithm = MATE_FIR; //当前分配算法为首次适配算法
int min_mem_size = 0;        //设置剩余分区过小的标志

//初始化空闲分区链表
FBT *Init_Free_Block(int mem_size){
    FBT *fb;
    fb = (FBT*)malloc(sizeof(FBT));
    if(fb==NULL){
        printf("No mem\n");
        return NULL;
    }
    fb->size = mem_size;
    fb->start_addr = MEM_START;
    fb->next = NULL;
    return fb;
}

void Rearrange_FIR(){              //首次适配算法，冒泡起始地址升序
    if(free_block == NULL || free_block->next == NULL)
        return;
    FBT *t1,*t2,*head;
    head = free_block;
    for(t1 = head->next;t1;t1 = t1->next){
        for(t2 = head;t2 != t1;t2=t2->next){
            if(t2->start_addr > t2->next->start_addr){
                int tmp = t2->start_addr;
                t2->start_addr = t2->next->start_addr;
                t2->next->start_addr = tmp;
                tmp = t2->size;
                t2->size = t2->next->size;
                t2->next->size = tmp;
            }
        }
    }
}
void Rearrange(int algorithm){  //按指定的算法整理内存空闲块链
    Rearrange_FIR();
}

int Display_Mem_Usage(){            //显示当前内存的使用情况
    FBT *fbt = free_block;
    AB *ab = allocated_block_head;
    printf("\e[0;31;1m------------------------------------------------------------------\e[0m\n");
    printf("\e[0;32;1m空闲的内存:\e[0m\n");       //空闲内存
    printf("\e[0;33;1m%20s %20s\e[0m\n","     start_addr","       size");
    while(fbt!=NULL){
        if(fbt->size!=0)
            printf("%20d %20d\n",fbt->start_addr,fbt->size);
        fbt = fbt->next;
    }
    printf("\n");
    printf("\e[0;35;1m使用的内存:\e[0m\n");       //已分配内存
    printf("\e[0;33;1m%10s %20s %20s %10s\e[0m\n","PID","ProcessName","start_addr","size");
    while(ab != NULL){
        printf("%10d %20s %20d %10d\n",ab->pid,ab->process_name,ab->start_addr,ab->size);
        ab = ab->next;
    }
    printf("\e[0;31;1m------------------------------------------------------------------\e[0m\n");
    return 0;
}
int Dispose(AB *free_ab){                  //释放链表ab节点
    AB *pre,*ab;
    if(free_ab == allocated_block_head){    //若释放首节点
        allocated_block_head = allocated_block_head->next;
        free(free_ab);
        return 1;
    }
    pre = allocated_block_head;             //否则
    ab = allocated_block_head->next;
    while(ab!=free_ab){
        pre = ab;
        ab = ab->next;
    }
    pre->next = ab->next;
    free(ab);
    return 2;
}
int Free_Mem(AB *ab){                //更新分区表归还已分配区，以及可能的合并
    int algorithm = ma_algorithm;
    FBT *fbt,*pre,*work;
    fbt = (FBT*)malloc(sizeof(FBT));
    if(!fbt) return -1;

    fbt->size = ab->size;
    fbt->start_addr = ab->start_addr; //插入链尾
    work = free_block;
    if(work == NULL){
        free_block = fbt;
        fbt->next == NULL;
    }else{
        while(work ->next != NULL){
            work = work->next;
        }
        fbt->next = work->next;
        work->next = fbt;
    }
    Rearrange_FIR();                   //首次适配算法
    pre = free_block;
    while(pre->next){
        work = pre->next;
        if(pre->start_addr + pre->size == work->start_addr ){
            pre->size = pre->size + work->size;
            pre->next = work->next;
            free(work);
            continue;
        }else{
            pre = pre->next;
        }
    }
    Rearrange(ma_algorithm);          //按照当前算法排序
    return 1;
}
AB *Find_Process(int pid){            //找到pid对应的链表节点
    AB *tmp = allocated_block_head;
    while(tmp != NULL){               //如果找不到
        if(tmp->pid == pid){
            return tmp;
        }
        tmp = tmp->next;
    }
    printf("Process with PID %d not found！\n",pid);
    return NULL;
}
int Kill_Process(int pid){           //释放进程内存
    AB *ab;
    ab = Find_Process(pid);
    if(ab!=NULL){
        Free_Mem(ab);                //释放分配表
        Dispose(ab);                 //释放节点
        return 0;
    }else{
        return -1;
    }
}
int Find_Free_Mem(int request){      //寻找非进程分配分区
    FBT *tmp = free_block;
    int mem_sum = 0;
    while(tmp){
        if(tmp->size >= request){    //若可以直接分配
            return 1;
        }
        mem_sum += tmp->size;
        tmp = tmp->next;
    }
    if(mem_sum >= request){          //若可以合并后分配
        return 0;
    }else{                           //若空间不足
        return -1;
    }
}
void Sort_AB(){                      //将已分配表按起始地址从大到小排序
    if(allocated_block_head == NULL || allocated_block_head->next == NULL)
        return;
    AB *t1,*t2,*head;
    head = allocated_block_head;
    for(t1 = head->next;t1;t1 = t1->next){
        for(t2 = head;t2 != t1;t2=t2->next){
            if(t2->start_addr > t2->next->start_addr){
                int tmp = t2->start_addr;
                t2->start_addr = t2->next->start_addr;
                t2->next->start_addr = tmp;
                tmp = t2->size;
                t2->size = t2->next->size;
                t2->next->size = tmp;
            }
        }
    }
}
void Reset_AB(int start){            //重新分配内存地址
    AB *tmp = allocated_block_head;
    while(tmp != NULL){
        tmp->start_addr = start;
        start += tmp->size;
        tmp = tmp->next;
    }
}
void  Memory_Compact(){             //进行内存紧缩
    FBT *fbttmp = free_block;
    AB *abtmp = allocated_block_head;
    int sum = 0;
    while(fbttmp!=NULL){            //检测剩余内存
        sum += fbttmp->size;
        fbttmp = fbttmp->next;
    }
    fbttmp = free_block;            //合并区块
    fbttmp->size = sum;
    fbttmp->start_addr = 0;
    fbttmp->next=NULL;
    FBT *pr = free_block->next;      //释放分区
    while(pr != NULL){
        fbttmp = pr->next;
        free(pr);
        pr = fbttmp;
    }
    Sort_AB();                      //已分配空间重新排序
    Reset_AB(sum);
}
void Do_Allocate_Mem(AB *ab){       //分配内存
    int request = ab->size;
    FBT *tmp = free_block;
    while(tmp != NULL){
        if(tmp->size >= request){
            ab->start_addr = tmp->start_addr;
            int residue = tmp->size - request;
            tmp->size = residue;
            tmp->start_addr = tmp->start_addr + request;
            return ;
        }
        tmp = tmp->next;
    }
}
int Allocate_Mem(AB *ab){          //分配内存应用
    FBT *fbt,*pre;
    int request_size=ab->size;
    fbt = pre = free_block;
    int f = Find_Free_Mem(request_size); //寻找可分配
    if(f == -1){                         //空闲内存不足
        printf("Not enough free memory!\n");
        return -1;
    }else{
        if(f == 0){                //内存紧缩后分配
            Memory_Compact();
        }
        Do_Allocate_Mem(ab);       //分配
    }
    Rearrange(ma_algorithm);       //重排空闲分区
    return 1;
}
int Alloc_Process(PRO prc){        //为进程分配内存
    AB *ab;
    int ret;
    ab = (AB*)malloc(sizeof(AB));
    if(!ab) exit(-5);
    ab->next=NULL;
    pid++;
    strcpy(ab->process_name,prc.process_name);
    ab->pid = pid;
    ab->size=prc.size+rand()%ALLOC_SIZE; //随机分配内存
    ret = Allocate_Mem(ab);              //分配内存，ret==1表示分配成功
    if((ret == 1) && (allocated_block_head == NULL)){ //若allocated_block_head尚未赋值
        allocated_block_head = ab;
        return 1;
    }else if(ret == 1){                  //分配成功
        ab->next = allocated_block_head;
        allocated_block_head = ab;
        return 2;
    }else if(ret == -1){                 //分配不成功
        printf("Fail!\n");
        free(ab);
        return -1;
    }
    return 3;
}

//初始化进程
void Init_Program(PRO prc[],int n)
{
    int i;
    for(i=0;i<n;++i){
        prc[i].size=PROCESS_SIZE;
        prc[i].pid=-1;
        sprintf(prc[i].process_name,"process-%02d",i+1);
    }
}

int main(int argc, char const *argv[]){
    int sel1,sel2;
    int total=0;                     //记录分配内存的次数
    free_block=Init_Free_Block(mem_size); //初始化空闲区
    PRO prc[PROCESS_NUM];            //存放要加载的进程
    Init_Program(prc,PROCESS_NUM);   //对这几个程进程进行初始化
    srand((unsigned)time(NULL));
    int i;
    for(i=0;i<DATA_NUM;++i)
    {
        sel1=rand()%2;
        int count=0;                  //统计三个进程中有多少个进程已经分配内存
        int j;
        for(j=0;j<PROCESS_NUM;++j){
            if(prc[j].pid!=-1)
                count++;
        }        //如果全部分配进程或者进程分配到达5次，那么就不能继续分配内存
        if((count==PROCESS_NUM && sel1==0)||total==5)
            sel1=1;                   //如果全部未分配进程，那么就不能继续释放内存
        if(count==0 && sel1==1)
            sel1=0;
        if(sel1==0)                    //为进程分配内存
        {                              //随机找到一个未分配内存的进程
            do{
                sel2=rand()%PROCESS_NUM;
            }while(prc[sel2].pid!=-1);
            Alloc_Process(prc[sel2]);  //分配内存空间
            prc[sel2].pid=pid;         //改变标记
            total++;
            Display_Mem_Usage();       //显示结果
        }
        else                           //释放进程占用的内存空间
        {
            do{                         //随机找到一个可释放进程
                sel2=rand()%PROCESS_NUM;
            }while(prc[sel2].pid==-1);
            Kill_Process(prc[sel2].pid);//释放内存空间
            prc[sel2].pid=-1;           //改变标记
            Display_Mem_Usage();        //显示
        }
    }
 }
